package com.code.test.first.stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * https://leetcode.cn/problems/sliding-window-maximum/submissions/532985313/
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.md
 * https://www.algomooc.com/635.html
 * 给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
 * <p>
 * 返回滑动窗口中的最大值。
 */
public class Code239 {

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int[] res = maxSlidingWindow(nums, 3);
        for (int i : res) {
            System.out.println(i + ",");
        }

    }

    public static int[] maxSlidingWindow2(int[] nums, int k) {
        int[] win = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length - k + 1; i++) {
            int max = Integer.MIN_VALUE;
            for (int j = i; j < i + k; j++) {
                //得出当前窗口的最大值
                max = Math.max(nums[j], max);
            }
            win[i] = max;
        }
        return win;
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 1) {
            return nums;
        }
        int len = nums.length - k + 1;
        int[] ret = new int[len];
        int num = 0;

        DecreaseQueue queue = new DecreaseQueue();
        //先将前k入队
        for (int i = 0; i < k; i++) {
            queue.add(nums[i]);
        }
        ret[num++] = queue.peek();

        for (int i = k; i < nums.length; i++) {
            //窗口开始滑动，要移除队列出口（最前面）的元素，移除时判断该元素是否放入队列
            /**
             * 这里是窗口往右移动，要移除最左侧元素
             */
            queue.poll(nums[i - k]);
            /**
             * 滑动窗口加入 nums[i]
             * 1,3,-1  -> [3] -> []
             */
            queue.add(nums[i]);
            ret[num++] = queue.peek();
        }


        return ret;
    }

}

/**
 * https://www.cxyxiaowu.com/14367.html
 */
class DecreaseQueue {

    Deque<Integer> queue = new LinkedList<>();

    public void poll(int val) {
        /**
         * 弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出
         * 同时判断队列当前是否为空
         *
         * 这里之所以要判断 val==queue.peek()
         * 是因为队列已经是单调递减的队列，如果不判断是否相等，则每次进来都会把最大的移除掉
         * 1, 3, -1, -3, 5, 3, 6, 7
         * [3,-1] (1,3,-1 这里的1一开始已经被3干掉，只剩 3，-1)
         * 所以窗口往右移动时
         * 第二个窗口右移后要移除的是1，但是1不再
         * 第3个窗口右移后要移除的是3，此时3是队首，可以移除
         *
         */
        if (!queue.isEmpty() && val == queue.peek()) {
            queue.poll();
        }
    }

    /**
     * <- ----出口----入口-------  <-
     */
    public void add(int val) {
        /**
         * 添加元素时，如果要添加的元素大于入口处的元素
         */
        while (!queue.isEmpty() && val > queue.getLast()) {
            queue.removeLast();
        }
        queue.addLast(val);
    }

    public int peek() {
        return queue.peek();
    }
}
